package com.wang.sort;

import java.util.Arrays;

/**
 * 排序算法
 * ===比较类排序===
 * 交换排序：冒泡排序、快速排序
 * 插入排序：插入排序、希尔排序
 * 选择排序：选择排序、堆排序
 * 归并排序：二路归并排序、多路归并排序
 * ===非比较类排序===
 * 计数排序
 * 桶排序
 * 基数排序
 */
public class SortTest {
    static final int[] arrays = new int[]{4, 6, 3, 2, 8, 9, 0, 5, 1, 7};

    public static void main(String[] args) {
        // 冒泡排序
        bubbleSort();
        // 快速排序
        quickSort();

        // 插入排序
        insertionSort();
        // 希尔排序
        shellSort();

        // 选择排序
        selectionSort();
        // 堆排序
        heapSort();
    }

    /**
     * 堆排序
     */
    private static void heapSort() {
    }

    /**
     * 希尔排序
     */
    private static void shellSort() {
    }

    /**
     * 插入排序
     * 像打扑克那样，将元素插入到合适的位置中，
     */
    private static void insertionSort() {
        int[] myArray = Arrays.copyOf(arrays, arrays.length);
        for (int i = 1; i < myArray.length; i++) {
            int preIndex = i - 1;
            int compare = myArray[i];
            while (preIndex >= 0 && myArray[preIndex] > compare) {
                myArray[preIndex + 1] = myArray[preIndex];
                preIndex--;
            }
            myArray[preIndex + 1] = compare;
        }
        Arrays.stream(myArray).forEach(str -> System.out.print(str + " "));
        System.out.println();
    }

    /**
     * 选择排序
     * 选取第一个元素为最小元素，拿后边的元素与之对比，查到最小元素，然后与头元素交换，保证头元素是有序的
     * 下次比较头N个元素无需参与
     */
    private static void selectionSort() {
        int[] myArray = Arrays.copyOf(arrays, arrays.length);
        for (int i = 0; i < myArray.length - 1; i++) {
            int min = i;
            for (int j = i + 1; j < myArray.length; j++) {
                if (myArray[j] < myArray[min]) {
                    min = j;
                }
            }
            if (min != i) {
                int temp = myArray[i];
                myArray[i] = myArray[min];
                myArray[min] = temp;
            }
        }
        Arrays.stream(myArray).forEach(str -> System.out.print(str + " "));
        System.out.println();
    }

    /**
     * 快速排序
     */
    private static void quickSort() {

    }

    /**
     * 冒泡排序
     * 每次比较相邻的两个元素，若前一个元素比后一个大，就交换他们的位置，这样每次比较后最大的元素都在最后
     * 下次比较末尾最大的N个元素不参与比较
     */
    public static void bubbleSort() {
        int[] myArray = Arrays.copyOf(arrays, arrays.length);
        for (int i = 1; i < myArray.length; i++) {
            for (int j = 0; j < myArray.length - i; j++) {
                if (myArray[j] > myArray[j + 1]) {
                    int var = myArray[j];
                    myArray[j] = myArray[j + 1];
                    myArray[j + 1] = var;
                }
            }
        }
        Arrays.stream(myArray).forEach(str -> System.out.print(str + " "));
        System.out.println();
    }
}
